The present invention pertains to a method for generating a digital roadmap that can be stored on an electronic storage medium and in which a geographical area is specified by a multitude of data sets. Besides, the present invention pertains to a navigation system that features a memory on which a digital roadmap of this type is stored and provided for use. Moreover, the present invention pertains to a method for operating a navigation system of the afore-mentioned type with a digital roadmap of the afore-mentioned type.
The core function of known navigation systems is based on the computation of routes from a starting point to a destination. Said computation thereby fundamentally relies on databases, in which the traffic routes of a specific geographical area are specified by means of a network of nodes and road elements linking said nodes. Besides, the road elements as such are specified in the database by means of road data sets in which a corresponding number of n reference points are stored. The position of the reference points thereby assumes the shape of the course of the respective road element. Each road data set is thereby required to contain at least two reference points (n=2), since each road element is required to feature at least one initial reference point and one final reference point.
Known route computation methods rely on a wave-like iterative procedure based on the starting point. The basic principle of said iterative procedures resides in the aspect that route costs are respectively computed for the various route alternatives in order to be able to evaluate the various route alternatives with respect to a specific value parameter, for instance the shortest route or the shortest time of travel. By means of the route cost computation the characteristic parameters in respect of which the route is supposed to be optimized are hence evaluated. The iterative methods for computing the route can thereby be initiated at the starting point or at the destination such that as a consequence, the search direction is irrelevant.
The problem to be solved according to the present invention is in literature referred to as the “Manhattan problem”. This problem results from the aspect that in conventional iteration methods for computing a route with respect to the shortest possible distance or with respect to the shortest possible time of travel, in case of cities featuring a road network with a clear-cut check pattern, routes that very frequently require alternating left and right turning maneuvers along the route are often the resultant output. This phenomenon, referred to as “zigzag routing”, is in principle undesirable, since the driver is required to execute a very large number of maneuvers along the predetermined route, even though, without entailing any significant drawbacks, another route along which a much smaller number of maneuvers would be sufficient could be traveled as well.
In order to eliminate said undesired zigzag routing, there are known navigation methods in which, in the route computation, a maneuver evaluation is performed for each maneuver executed at a node between at least two road elements. As a result of said maneuver evaluation, a maneuver cost value is subsequently computed for the corresponding maneuver and is incorporated into the route computation. Route alternatives with an overall lower maneuver cost value that results from the sum of all individual maneuver cost values are subsequently prioritized over route alternatives with an overall higher maneuver cost value.
For computing the maneuver cost values, various approaches are known from the state of the art. In line with a first problem-solution approach, intersection tables are stored in the database for specifying the road network in the relevant area. Said intersection tables hence contain the corresponding intermediate angles or a maneuver cost value derived therefrom for each combination of two road elements positioned at a node. In computing the individual route alternatives, said corresponding maneuver cost values are subsequently read out from the intersection tables and are taken into consideration in the evaluation of the individual route alternatives. Said intersection tables are afflicted with the drawback that the databases for storing the road network become heavily bloated. In addition, considerable computing capacity is required for the evaluation of the intersection tables so that the required hardware is either extremely expensive or else, the corresponding route computation methods are significantly slowed down.
Alternatively to storing intersection tables, it is likewise known that the intersection geometry in the individual nodes is analyzed during the computation of the individual route alternatives by evaluating the geometry of the route trajectories and that the respective angles between two road elements are derived therefrom. This problem-solution approach does in fact provide advantages with respect to the database size, since no additional data are required to be stored. However, the evaluation of the geometry of the route trajectories at the intersection points is very complex so that the computation speed for the route alternatives is undesirably long.